package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 513. 找树左下角的值
 * 剑指 Offer II 045. 二叉树最底层最左边的值
 *
 * @Author liw
 * @Date 2021/5/11 14:07
 * @Version 1.0
 */
public class FindBottomLeftValue {

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> a = new ArrayDeque<>();
        Queue<TreeNode> b = new ArrayDeque<>();
        a.add(root);
        while (!a.isEmpty() ) {
            TreeNode first = ((ArrayDeque<TreeNode>) a).getFirst();
            while (!a.isEmpty()) {
                TreeNode poll = a.poll();
                if (poll.left != null) {
                    b.add(poll.left);
                }
                if (poll.right != null) {
                    b.add(poll.right);
                }
            }
            if (b.isEmpty()) {
                return first.val;
            }
            a = b;
            b = new ArrayDeque<>();
        }
        return 0;
    }
}
